#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <malloc.h>
#include "tree0.h"

typedef struct{
	Node *parent;
	Node *child;
}Pair;

static Pair seekItem(const Item *pitem,Tree *ptree);
static BOOL toLeft(const Item *l1,const Item *l2);
static BOOL toRight(const Item *l1,const Item *l2);
static Node *makeNode(const Item *pitem);
static BOOL addNode(Node *new_node,Node *root);
static void inorder(const Node *root,Pfun fun);
static void deleteNode(Node **ppnode);
static void deleteAllNodes(Node *root);

void createTree(Tree *ptree)
{
	ptree->root = NULL;
	ptree->size = 0;
}

BOOL treeIsEmpty(const Tree *ptree)
{
	if (ptree->root == NULL){
		return TRUE;
	}
	return FALSE;
}

BOOL treeIsFull(const Tree *ptree)
{
	if (ptree->size == MAX_TSIZE)
		return TRUE;
	return FALSE;
}

int treeCount(const Tree *ptree)
{
	return ptree->size;
}

BOOL treeAddItem(const Item *pitem,Tree *ptree)
{
	Node *new_node;

	if (treeIsFull(ptree)){
		fprintf(stderr,"The tree is full\n");
		return FALSE;
	}
	if (inTree(pitem,ptree)){
		fprintf(stderr,"The item already in the tree!\n");
		return TRUE;
	}

	new_node = makeNode(pitem);
	if (new_node == NULL){
		fprintf(stderr,"Can't malloc memory!\n");
		return FALSE;
	}

	ptree->size++;
	if (treeIsEmpty(ptree)){
		ptree->root = new_node;
		return TRUE;
	}

	return addNode(new_node,ptree->root);
}

BOOL inTree(const Item *pitem,Tree *ptree)
{
	return ((seekItem(pitem,ptree).child == NULL)?FALSE:TRUE);  
}

void traverse_tree(const Tree *ptree,Pfun fun)
{
	if (ptree != NULL){
		inorder(ptree->root,fun);
	}
}

BOOL deleteItem(const Item *pitem,Tree *ptree)
{
	Pair look;
	look = seekItem(pitem,ptree);
	if (look.child == NULL){
		return FALSE;
	}
	if (look.parent == NULL){
		deleteNode(&ptree->root);
	}
	else if (look.parent->left == look.child){
		deleteNode(&look.parent->left);
	}
	else
		deleteNode(&look.parent->right);
	ptree->size--;
	return TRUE;
}

void deleteAll(Tree *ptree)
{
	if (ptree != NULL){
		deleteAllNodes(ptree->root);
	}
	ptree->root = NULL;
	ptree->size = 0;
}

static Pair seekItem(const Item *pitem,Tree *ptree)
{
	Pair look;
	look.parent = NULL;
	look.child = ptree->root;

	if (look.child == NULL){
		return look;
	}

	while(look.child != NULL){
		if (toLeft(pitem,&(look.child->item))){
			look.parent = look.child;
			look.child = look.child->left;
		}
		else if (toRight(pitem,&(look.child->item))){
			look.parent = look.child;
			look.child = look.child->right;
		}
		else
			break;  // the item in the tree,break
	}
	return look;
}
/*
static BOOL toLeft(const Item *l1,const Item *l2)
{
	if (STRCMP(l1->petname,>,l2->petname)){
		return FALSE;
	}
	if (STRCMP(l1->petname,<,l2->petname) || 
			STRCMP(l1->petkind,<,l2->petkind))
		return TRUE;
	return FALSE;
}

static BOOL toRight(const Item *l1,const Item *l2)
{
	if (STRCMP(l1->petname,<,l2->petname)){
		return FALSE;
	}
	if (STRCMP(l1->petname,>,l2->petname) || 
			STRCMP(l1->petkind,>,l2->petkind))
		return TRUE;
	return FALSE;
}
*/

static BOOL toLeft(const Item *l1,const Item *l2)
{
	if (COMPARE(l1->data,l2->data) == LESS){
		return TRUE;
	}
	return FALSE;
}

static BOOL toRight(const Item *l1,const Item *l2)
{
	if (COMPARE(l1->data,l2->data) == MORE){
		return TRUE;
	}
	return FALSE;
}

static Node *makeNode(const Item *pitem)
{
	Node *pnode = NULL;

	pnode = (Node *)malloc(sizeof(Node));
	if (pnode != NULL){
		pnode->item = *pitem;
		pnode->left = NULL;
		pnode->right = NULL;
	}

	return pnode;
}

static BOOL addNode(Node *new_node,Node *root)
{
	if (new_node == NULL){
		fprintf(stderr,"new_node is NULL\n");
		return FALSE;
	}
	if (root == NULL){
		fprintf(stderr,"root is NULL\n");
		return FALSE;
	}

	if (toLeft(&new_node->item,&root->item)){
		if (root->left == NULL){
			root->left = new_node;
			return TRUE;
		}
		else{
			return addNode(new_node,root->left);
		}
	}
	else if (toRight(&new_node->item,&root->item)){
		if (root->right == NULL){
			root->right = new_node;
			return TRUE;
		}
		else{
			return addNode(new_node,root->right);
		}
	}
	else{
		fprintf(stderr,"Can't addNode\n");
		return FALSE;
	}
	return TRUE;
}

static void inorder(const Node *root,Pfun fun)
{
	if (root != NULL){
		inorder(root->left,fun);
		fun(root->item);
		inorder(root->right,fun);
	}
}

static void deleteNode(Node **ppnode)
{
	Node *psave;
	if ((*ppnode)->left == NULL){
		psave  = *ppnode;
		*ppnode = (*ppnode)->right;
		free(psave);
	}
	else if ((*ppnode)->right == NULL){
		psave = *ppnode;
		*ppnode = (*ppnode)->left;
		free(psave);
	}
	else{
		for(psave = (*ppnode)->left;psave->right != NULL;
				psave = psave->right)
			continue;
		psave->right = (*ppnode)->right;
		psave = *ppnode;
		*ppnode = (*ppnode)->left;
		free(psave);
	}
}

static void deleteAllNodes(Node *root)
{
	Node *pright;

	if (root != NULL){
		pright = root->right;
		deleteAllNodes(root->left);
		free(root);
		deleteAllNodes(pright);
	}
}

